The core challenge is visiting every reachable node exactly once, which requires a clear rule for what to visit next.

  • The goal is to visit all vertices reachable from a start node s while avoiding revisits.
  • This requires a visited set to track which nodes have been seen.
  • A rule is needed to choose the "next" node to process from the frontier of discovered nodes.
  • BFS uses a FIFO (First-In, First-Out) rule with a queue, processing the oldest discovered node.
  • DFS uses a LIFO (Last-In, First-Out) rule with a stack or recursion, processing the newest discovered node.
  • The choice of data structure (queue vs. stack) fundamentally defines the traversal's order and behavior.
High-Level Traversal Algorithm (Python)
def traversal(graph, start_node):
    # For BFS, use collections.deque(). For DFS, a list is fine.
    frontier = [start_node]
    visited = {start_node}

    while frontier:
        # For a Queue (BFS): current_node = frontier.pop(0)
        # For a Stack (DFS): current_node = frontier.pop()
        current_node = frontier.pop(0)
        process(current_node)
        
        for neighbor in graph[current_node]:
            if neighbor not in visited:
                visited.add(neighbor)
                frontier.append(neighbor)